HDU_5832

描述

给一个图染色，要求他的联通子集是唯一的颜色，求他每个子集的着色数再乘233^ith

思路

先n^2*2^n计算出所有的不联通子集和连通子集，只要有一点边连通两个点就算是连通子集，即sub[i]作区分。然后枚举所有子集A，再枚举A的子集B(子集的子集),每出现一只不连通的子集B，就转移一下状态。

解释

hdu5832

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
bool sub[1<<20];
int dp[1<<20];
char mp[20][20];
int main(){
    int t;for(cin>>t;t--;){
        int n;memset(mp,0,sizeof(mp));cin>>n;
        memset(sub,0,sizeof(sub));
        for(int i=0 ; i < n ; i++)
            scanf("%s",mp[i]);
        int len=(1<<n) -1;
        //求连通子集
        for(int i=1; i<=len ; i++){
            for(int j=0 ; j<n ; j++)
                if((i>>j)&1){
                    for(int k=0 ; k<n ;k++){
                        if(sub[i])break;
                        if((i>>k)&1 && mp[j][k]=='1'){
                            sub[i]=1;break;
                        }
                        if(sub[i])break;
                    }
                }
        }
        memset(dp,0X3f3f3f,sizeof(dp));
        dp[0]=0;
        //求子集的子集
        for(int i=1 ; i<=len ; i++){
            for(int j=i ; j ; j=(j-1)&i){
                if(!sub[j]){
                    dp[i]=min(dp[i],dp[i ^ j]+1);
                }
            }
        }
        unsigned int pre=1 , ans=0;
        for(int i=1 ; i<=len ; i++){
            pre*=233;
            ans+=pre*dp[i];
        }
        printf("%u\n",ans);
    }
    return 0;
}